package com.fanwh.sparsearray;

import java.util.Scanner;

/**
 * @program: DataStructure
 * @description: 稀疏数组与原始数组的转换——当数组中存在大量相同元素时，即可考虑使用稀疏数组简化原始数组的存储
 * @author: Fanwh
 * @create: 2020-09-13 22:37
 **/
public class SparseArray {

    /**
     * @Description: 原始数组 ——> 稀疏数组
     *  思路：
     *  1.遍历二维原始数组，找到原始数组中有效数据的个数sum；
     *  2.创建稀疏数组，int[][] SparseArray = new int [sum+1][3];
     *  3.将有效数据存入稀疏数组中。
     * @Param: [a]
     * @return: int[][]
     * @Author: Fanwh
     * @Date: 2020/9/13
     */
    public int[][] getSparseArray(int[][] a){
        int sum =0;
        for (int i = 0;i<a.length;i++){
            for(int j = 0;j<a[i].length;j++){
                if(a[i][j] != 0){
                    sum++;
                }
            }
        }
        int[][] SparseArray = new int [sum+1][3];
        SparseArray[0][0] = a.length;
        SparseArray[0][1] = a[0].length;
        SparseArray[0][2] = sum;
        int count = 0;
        for (int i = 0;i<a.length;i++){
            for (int j = 0;j<a[i].length;j++){
                if(a[i][j] != 0){
                    count++;
                    SparseArray[count][0] = i;
                    SparseArray[count][1] = j;
                    SparseArray[count][2] = a[i][j];
                }
            }
        }
        return SparseArray;
    }
    /**
     * @Description: 稀疏数组 ——> 原始数组
     * 思路
     * 1.读取稀疏数组第一行，通过sparsearray[0][0]、sparsearray[0][1]创建原始数组大小；
     * 2.读取稀疏数组后面几行，将后面几行的值付给新的数组;
     * @Param: [sparsearray]
     * @return: int[][]
     * @Author: Fanwh
     * @Date: 2020/9/13
     */
    public int[][] getOriginalArray(int[][] sparsearray){
        int[][] OrignalArray = new int [sparsearray[0][0]][sparsearray[0][1]];
        for (int i = 1;i<sparsearray.length;i++){
            OrignalArray[sparsearray[i][0]][sparsearray[i][1]] = sparsearray[i][2];
        }
        return OrignalArray;
    }
    public static void main(String[] args) {
        SparseArray test = new SparseArray();
        //确定原始数组的规模
        System.out.println("原始数组的行：");
        Scanner scan = new Scanner(System.in);
        int row = scan.nextInt();
        System.out.println("原始数组的列：");
        int col = scan.nextInt();
        //输入原始数组的具体数据
        int[][] orginalArray = new int[row][col];
        System.out.println("给数组赋值：");
        for (int i = 0; i<row;i++){
            for (int j = 0;j<col;j++){
                orginalArray[i][j] = scan.nextInt();
            }
        }
        //输出原始数组
        System.out.println();
        System.out.println("原始数组为：");
        for(int[] row1:orginalArray){
            for(int data:row1){
                System.out.print(data+"\t");
            }
            System.out.println();
        }

        //测试输出稀疏数组
        int[][] sparseArray =  test.getSparseArray(orginalArray);
        System.out.println();
        System.out.println("稀疏数组为：");
        for(int[] row1:sparseArray){
            for(int data:row1){
                System.out.print(data+"\t");
            }
            System.out.println();
        }

        //测试恢复原始数组
        SparseArray test1 = new SparseArray();
        int[][] originalarray = test1.getOriginalArray(sparseArray);
        System.out.println();
        System.out.println("恢复的原始数组为：");
        for(int[] row1:originalarray){
            for(int data:row1){
                System.out.print(data+"\t");
            }
            System.out.println();
        }
    }
}
